
//437.路径总和III
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    //使用递归来完成,但是要记录来时的路
    int dfs(TreeNode* node,int tar,unordered_map<long long,int>& m,long long sum)
    {
        if(node == nullptr) return 0;
        sum += node -> val;                         //将该位置值加入到路径总和中
        int ret = 0;
        if(m.count(sum - tar)) ret += m[sum-tar];   //在前面路径中查找
        m[sum]++;                                   //将该位置路径加入到哈希表中,继续递归
        ret += dfs(node->left,tar,m,sum)  +dfs(node->right,tar,m,sum);
        if(--m[sum]==0) m.erase(sum);               //恢复,往回返回
        
        return ret;
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long,int> m;             //记录每个路径的和及个数
        m.insert({0,1});
        return dfs(root,targetSum,m,0);
    }
};